[UOJ513]-清扫银河

思维, 高斯消元

官方题解 逻辑很清晰！

若有解则必然可以在 m + 1 次操作里出解。

证明：
首先要知道一个性质：无向图的任何环都可以由若干个非树边覆盖的环异或得到。也就是说有用的操作一只有 m - n + 1 个。

而操作二等价于每次选一个点，将与这个点相邻的边全部反转，也就是说有用的操作二有 n 个。

总共操作数为 m + 1 个，解异或方程组，必然可以在 m + 1 次操作里出解，况且多个操作二还可以合成一个呢。

但真的这样做却是 O(m^3 / 32) 的，考虑优化。

将所有 1 边形成的图称为目标子图。

根据欧拉回路的知识，若目标子图中每个节点的度数都是偶数，则必然可以通过不超过 m - n + 1 次操作一将边权都变成 0.

因此只要考虑，仅用操作二能否让目标子图中每个节点度数变成偶数。

这样是 O(n^3 / 32) 的。

异或什么的想想方程组啊，，，虽然暴力，但到底是个切入口。不过后续就需要找性质了。

正式做题时，逆推回去比较好：环上点的度数都是偶数…所以blabla

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 305;
int T, n, m;
bitset<N> a[N], x;

bool Gauss() {
    rep(i, 1, n) {
        if (!a[i][i]) {
            rep(j, i + 1, n) if (a[j][i]) { swap(a[i], a[j]); break; }
            if (!a[i][i]) continue;
        }
        rep(j, i + 1, n) if (a[j][i]) a[j] ^= a[i];
    }
    for (int i = n; i; --i) {
        int t = a[i][n + 1];
        rep(j, i + 1, n) t ^= (a[i][j] * x[j]);
        if (!a[i][i] && t) return 0;
        x[i] = t;
    } return 1;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m;
        rep(i, 1, m) {
            int x, y, z; scanf("%d%d%d", &x, &y, &z);
            a[x][x].flip(), a[y][y].flip(), a[x][y] = 1, a[y][x] = 1;
            if (z) a[x][n + 1].flip(), a[y][n + 1].flip();
        }
        puts(Gauss() ? "yes" : "no");
        rep(i, 1, n) a[i].reset();
        x.reset();
    }
    return 0;
}